﻿using System;
using System.Linq;
using System.Numerics;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Fourier
{
    public class RecursiveFastFourierTransform : IDiscreteFourierTransform
    {
        private readonly IList<Complex> _w;

        public RecursiveFastFourierTransform(int N)
        {
            _w = Enumerable.Repeat(new Complex(0, 0), N+1).ToAlgoritmiaList();
            int i = 1;
            while (i <= N)
            {
                _w[i] = Complex.Exp(new Complex(0, 2 * Math.PI) / i);
                i *= 2;
            }
        }

        #region Implementation of IDiscreteFourierTransform

        public IList<Complex> Transform(IList<Complex> complexs)
        {
            int n = complexs.Count;
            if (n == 1)
                return complexs;
            var even = Transform(complexs.Where((c, i) => i%2 == 0).ToAlgoritmiaList());
            var odd = Transform(complexs.Where((c, i) => i%2 == 1).ToAlgoritmiaList());
            return (from k in Enumerable.Range(0, n)
                    select even[k%(n/2)] + Complex.Pow(_w[n], -k)*odd[k%(n/2)]).ToAlgoritmiaList();
        }

        #endregion
    }
}
